// step 1# 定义比较函数，用于 qsort 排序
int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b; // 升序排序
}

// step 2# 主函数：查找所有和为 0 的三元组
int** threeSum(int* nums, int n, int* returnSize, int** returnColumnSizes) {
    // step 2.1# 先对数组排序
    qsort(nums, n, sizeof(int), cmp); // 排序是为了使用双指针

    // step 2.2# 分配足够空间存放所有可能的三元组
    int** ans = malloc(n * n * sizeof(int*));               // 存放结果三元组数组
    *returnColumnSizes = malloc(n * n * sizeof(int));       // 存放每组结果长度（固定为 3）
    int m = 0; // 当前已找到的三元组数量

    // step 3# 枚举第一个数 nums[i]
    for (int i = 0; i < n - 2; i++) {
        int x = nums[i];

        // step 3.1# 去重：跳过与前一个相同的元素
        if (i > 0 && x == nums[i - 1]) continue;

        // step 3.2# 优化剪枝：最小三数之和已大于 0，后续不可能为 0，提前结束
        if (x + nums[i + 1] + nums[i + 2] > 0) break;

        // step 3.3# 优化剪枝：当前 x 和最大的两个数还不够为 0，跳过
        if (x + nums[n - 2] + nums[n - 1] < 0) continue;

        // step 4# 使用双指针寻找剩余两个数
        int j = i + 1, k = n - 1;

        while (j < k) {
            int s = x + nums[j] + nums[k]; // 三数之和

            if (s > 0) {
                k--; // step 4.1# 和太大，右指针左移
            } else if (s < 0) {
                j++; // step 4.2# 和太小，左指针右移
            } else {
                // step 4.3# 找到一组满足条件的三元组
                int* tuple = malloc(3 * sizeof(int)); // 为三元组分配空间
                tuple[0] = x;
                tuple[1] = nums[j];
                tuple[2] = nums[k];
                ans[m] = tuple;                        // 存入结果数组
                (*returnColumnSizes)[m++] = 3;         // 记录该行长度为 3

                // step 4.4# 跳过重复元素，避免结果重复
                for (j++; j < k && nums[j] == nums[j - 1]; j++);
                for (k--; k > j && nums[k] == nums[k + 1]; k--);
            }
        }
    }

    // step 5# 设置返回结果的大小
    *returnSize = m;
    return ans; // 返回最终的三元组数组
}
